#include <iostream>
#include <vector>
using namespace std;

void buildLPS(string pattern, vector<int>& lps) {
    int n = pattern.length();
    int len = 0;
   
    lps[0] = 0;
    int i = 1;
   
    while (i < n) {
        if (pattern[i] == pattern[len]) {
            len++;
            lps[i] = len;
            i++;
        }
        else {
            if (len != 0) {
                len = lps[len - 1];
            }
            else {
                lps[i] = 0;
                i++;
            }
        }
    }
}

int kmpPatternMatching(string text, string pattern) {
    int count = 0;
    int m = text.length();
    int n = pattern.length();
   
    vector<int> lps(n, 0);
    buildLPS(pattern, lps);

    int i = 0; 
    int j = 0; 
   
    while (i < m) {
        if (pattern[j] == text[i]) {
            j++;
            i++;
        }

        if (j == n) {
            count++; 
            j = lps[j - 1];
        }
        else if (i < m && pattern[j] != text[i]) {
            if (j != 0) {
                j = lps[j - 1];
            }
            else {
                i++;
            }
        }
    }
   
    return count;
}

int main() {
    string text = "ABABAABABABAABA";
    string pattern = "ABA";

    int result = kmpPatternMatching(text, pattern);
    
    cout << "The number of non-overlapping occurrences of the pattern in the text is: " << result << endl;

    return 0;
}